<?php
/**
 * 一致性hash的PHP实现
 */

//需要一个把字符串转成整数的功能
interface hash{
    public function _hash($str);
}

interface distribution{
    //增加节点
//    public addNote($node);
    //查找节点
    public function lookup($key);
}
/**取模算法类**/
class Moder implements hash,distribution{
    protected $_nodes = array();   //节点数组
    protected $_cnt = 0;            //节点的个数
    public function _hash($str){
        return sprintf('%u',crc32($str));  //把字符串转成32位符号整数
    }

    /**
     * 添加节点
     * @param $node 节点
     * @return bool
     */
    public function addNode($node){
        //如果节点已经存在，不添加
        if(in_array($node,$this->_nodes)){
            return true;
        }
        $this->_nodes[] = $node;   //将节点压入节点数组
        $this->_cnt += 1;          //节点数加1
        return true;
    }

    /**
     * 删除节点
     * @param $node  节点
     * @return bool
     */
    public function delNode($node){
        //如果节点不存在，不执行删除
        if(!in_array($node,$this->_nodes)){
            return true;
        }
        //查找节点在节点数组中对应的key值
        $key = array_search($node,$this->_nodes);
        //删除节点
        unset($this->_nodes[$key]);
        $this->_nodes = array_merge($this->_nodes);  //重新从0对索引排序
        $this->_cnt -= 1;  //节点减1
        return true;
    }

    /**
     * 查找节点
     * @param $key key值
     * @return mixed
     */
    public function lookup($key){
        $key = $this->_hash($key) % $this->_cnt;
        return $this->_nodes[$key];
    }
}
/**哈希类**/
class Consistent implements hash,distribution{
    protected $_nodes = array();   //存放memcached服务器节点
    protected $_mul = 64;   //虚拟节点
    protected $position = array();  //存放虚节点
    public function _hash($str){
        return sprintf('%u',crc32($str));  //把字符串转成32位符号整数
    }

    /**
     * 查找服务器节点（核心功能）
     * @param $key
     */
    public function lookup($key){
        $point = $this->_hash($key);
        //计算$key应该落在哪一个节点上

        $node = current($this->position); //先取圆环上最小的一个节点，当成结果
        foreach($this->position as $k=>$v){
            if($point <= $k){
                $node = $v;
                break;
            }
        }
        return $node;
    }

    /**
     * 添加一个节点
     * param $node localhost:端口
     **/
    public function addNode($node){
        for($i=0;$i<$this->_mul;$i++){
            $this->position[$this->_hash($node . '-' . $i)] = $node; //虚节点
        }
        $this->_nodes[$this->_hash($node)] = $node;   //记录节点的位置
        //排序
        $this->_sortPos();
    }
    /**循环所有的虚节点，谁的值==指定的真实节点，就把他删掉**/
    public function delNode($node){
        foreach($this->position as $k=>$v){
            if($v == $node){
                unset($this->position[$k]);
            }
        }
    }

    /**按照键名对节点数组进行排序**/
    public function _sortNode(){
        ksort($this->_nodes,SORT_REGULAR);
    }

    public function _sortPos(){
        ksort($this->position,SORT_REGULAR);
    }
    /*
    public function printNodes(){
        print_r($this->_nodes);
    }*/

    public function printPos(){
        print_r($this->position);
    }
}

//$con = new Moder();
//$con->addNode('a');
//$con->addNode('b');
//$con->addNode('c');
/**
echo '所有的服务器如下:<br/>';
$con->test();
 **/
//echo '当前的键计算的hash落点是' . $con->_hash('title') . '<br/>';

//echo $con->lookup('title');
?>
